Mobile devices are rich in sensors. For example, mobile devices often include a Global Positioning System (GPS) tracker, microphone, and camera. Mobile devices also often have access to numerous sources of personal information including the device ID, contacts, and social data of a user. This richness of information increases the functionality of mobile applications running on the mobile device but also creates privacy threats. The balance between privacy and functionality is subtle, as the user clearly wishes to maximize both. For example, an e-commerce application with offerings and promotions based on the user's location would often like to transmit the user's city or zip code from the user's mobile device to its server. The privacy loss of such a transmission is marginal (city and zip code are considered coarse location information) and in return useful contextual functionality is enabled for the e-commerce application, e.g., promotions and offerings to local stores. On the other hand, sharing fine-grained location information with the e-commerce application's server, such as, for example, the user's exact GPS coordinates, may be unjustified.